#include <iostream>
using namespace std;

#define N 5 // 定义迷宫的大小为5x5

// 迷宫地图，1表示墙壁，0表示路径
int maze[N][N] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}};

// 方向数组，表示上下左右移动
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 标记是否访问过，防止重复访问
int visited[N][N] = {0};

// 打印路径的函数
void printPath(int path[N][N], int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            cout << path[i][j] << " ";
        }
        cout << endl;
    }
}

// 深度优先搜索函数
int dfs(int x, int y, int path[N][N])
{
    if (x == N - 1 && y == N - 1)
    {
        path[x][y] = 9;
        printPath(path, N);
        return 1;
    }
    // 标记当前节点为路径一部分，并标记为3（已访问）
    visited[x][y] = 3;
    path[x][y] = 6;

    // 尝试四个方向
    for (int i = 0; i < 4; i++)
    {
        int newX = x + direction[i][0];
        int newY = y + direction[i][1];
        if (newX >= 0 && newX < N && newY >= 0 && newY < N && maze[newX][newY] == 0 && !visited[newX][newY])
        {
            // 递归调用dfs函数
            if (dfs(newX, newY, path))
            {
                return 1;
            }
        }
    }
    // 无法继续前进
    path[x][y] = 0;
    return 0;
}

int main()
{
    int path[N][N] = {0}; // 所有位置初始为0，表示未访问
    // 从（0,0）开始深度优先搜索
    if (!dfs(0, 0, path))
    {
        cout << "NO Path found!" << endl;
    }
    return 0;
}